#include <stdio.h>
#include <malloc.h>

#define INF     32767              
#define MAXV    100                

typedef char InfoType;
typedef struct
{
    int no;                        
    InfoType info;               
}VertexType;                      

typedef struct
{
    int edges[MAXV][MAXV];         
    int n;                          
    int e;                        
    VertexType vexs[MAXV];       
}MatGraph;                       

typedef struct ArcNode
{
    int adjvex;                    
    struct ArcNode *nextarc;       
    int weight;                    
}ArcNode;                          

typedef struct VNode
{
    InfoType info;              
    int cnt;                       
    ArcNode *firstarc;              
}VNode;                            

typedef struct
{
    VNode adjlist[MAXV];          
    int n;                        
    int e;                        
}AdjGraph;                         

void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e)
{
    int i, j;

    g.n = n;
    g.e = e;
    for(i = 0; i < g.n; i++)
        for(j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g)
{
    int i, j;
    for(i = 0; i < g.n; i++)
    {
        for(j = 0; j < g.n; j++)
        {
            if(g.edges[i][j] != INF)
                printf("%4d", g.edges[i][j]);
            else
                printf("%4s", "∞");
        }
        printf("\n");
    }
}

void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
    int i, j;
    ArcNode *p;
    G = (AdjGraph *)malloc(sizeof(AdjGraph));
    for(i = 0; i < n; i++)                             
    {
        G->adjlist[i].firstarc = NULL;
    }
    for(i = 0; i < n; i++)                             
    {
        for(j = n - 1; j >= 0; j--)
        {
            if(A[i][j] != 0 && A[i][j] != INF)        
            {
                p = (ArcNode *)malloc(sizeof(ArcNode)); 
                p->adjvex = j;                          
                p->weight = A[i][j];                    
                p->nextarc = G->adjlist[i].firstarc;    
                G->adjlist[i].firstarc = p;
            }
        }
    }
    G->n = n;
    G->e = e;
}

void DispAdj(AdjGraph *G)
{
    ArcNode *p;
    for(int i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        printf("顶点%d: ", i);
        while(p != NULL)
        {
            printf("%3d[%d]->", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("∧\n");
    }
}

void DestroyAdj(AdjGraph *&G)
{
    ArcNode *pre, *p;

    for(int i = 0; i < G->n; i++)
    {
        pre = G->adjlist[i].firstarc;                  
        if(pre != NULL)
        {
            p = pre->nextarc;
            while(p != NULL)                         
            {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);                                           
}

static void Dispath(MatGraph g, int A[][MAXV], int path[][MAXV])
{
    int i, j, k, s;
    int apath[MAXV], d;                          

    for(i = 0; i < g.n; i++)
    {
        for(j = 0; j < g.n; j++)
        {
            if((i != j) && (A[i][j] != INF))        
            {
                printf("  从%d到%d的路径为:", i, j);
                k = path[i][j];
                d = 0; apath[d] = j;               
                while((k != -1) && (k != i))       
                {
                    d++;
                    apath[d] = k;
                    k = path[i][k];
                }
                d++; apath[d] = i;                 
                printf("%d", apath[d]);             
                for(s = d - 1; s >= 0; s--)       
                    printf(",%d", apath[s]);
                printf("    \t路径长度为:%d\n", A[i][j]);
            }
        }
    }
}

static void Floyd(MatGraph g)
{
    int A[MAXV][MAXV], path[MAXV][MAXV];
    int i, j, k;

    for(i = 0; i < g.n; i++)
    {
        for(j = 0; j < g.n; j++)
        {
            A[i][j] = g.edges[i][j];
            if((i != j) && (g.edges[i][j] < INF))
            {
                path[i][j] = i;                    
            }
            else
            {
                path[i][j] = -1;                 
            }
        }
    }

    for(k = 0; k < g.n; k++)                    
    {
        for(i = 0; i < g.n; i++)
        {
            for(j = 0; j < g.n; j++)
            {
                if(A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];   
                    path[i][j] = path[k][j];       
                }
            }
        }
    }

    Dispath(g, A, path);
}

int main(void)
{
    MatGraph g;
    int A[MAXV][MAXV] = {
        {0, 5, INF, 7, INF, INF},
        {INF, 0, 4, INF, INF, INF},
        {8, INF, 0, INF, INF, 9},
        {INF, INF, 5, 0, INF, 6},
        {INF, INF, INF, 5, 0, INF},
        {3, INF, INF, INF, 1, 0}
    };
    int n = 6;
    int e = 10;        
    CreateMat(g, A, n, e);      
    printf("有向图G的邻接矩阵:\n");
    DispMat(g);
    printf("弗洛伊德算法求解结果:\n");
    Floyd(g);
    return 0;
}
